package xyz.scootaloo.oj.leetcode

import org.junit.Test
import xyz.scootaloo.common.TestDsl
import kotlin.math.max

/**
 * @author flutterdash@qq.com
 * @since 2021/7/3 15:00
 */
class P53 : TestDsl {

    private fun maxSubArray(nums: IntArray): Int {
        val size = nums.size
        val dp = IntArray(size)
        dp[0] = nums[0]

        var max = dp[0]
        for (i in 1 until size) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
            if (dp[i] > max)
                max = dp[i]
        }

        return max
    }

    @Test
    fun test0() {
        maxSubArray(intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)) shouldBe 6
        maxSubArray(intArrayOf(1)) shouldBe 1
        maxSubArray(intArrayOf(0)) shouldBe 0
        maxSubArray(intArrayOf(-1)) shouldBe -1
        maxSubArray(intArrayOf(-1000000)) shouldBe -1000000
    }

}
